package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by tiang on 2018/9/8.
 * 字符串中只包括'b'和'w'两个字符，合法的字符串是b和w相间，即bwbw这种格式的字符串
 * 给定一个目标字符串，可以将其切割一刀，然后将两个子串分别翻转再重新拼接，也可以不操作
 * 求操作n次之后，最终得到的字符串中合法子串的最长长度
 */
public class ReverseStringAndNotRepeat {
    /**
     * 查找字符串中的最大不重复子串长度
     * @param str 源字符串
     * @return 最大长度
     */
    private int getMax(String str){
        int sum = 1;
        int max = 0;
        for(int i=1;i<str.length();i++){
            // 如果当前字符与前一个字符不相同，长度+1
            if(str.charAt(i) != str.charAt(i-1))
                sum ++;
            else{
                // 如果相同，查看是否是最大长度
                max = Integer.max(max, sum);
                sum = 1;
            }
        }
        return Integer.max(max, sum);
    }

    /**
     * 经过切割翻转之后，能得到的最大不重复子串的长度
     * @param str 源字符串
     * @return 最大长度
     */
    public int findMaxNotReaptString(String str){
        int result = 0;
        // 如果首尾两个字符相同，切割没有意义，因为切割之后翻转，中间两个字符变成首尾字符，仍然相同，长度不会增加
        if(str.charAt(0) == str.charAt(str.length()-1)){
            result = getMax(str);
        }else{
            int max = getMax(str);
            // 记录每一个重复字符的位置
            List<Integer> samePoint = new ArrayList<>();
            for(int i=1;i<str.length();i++){
                if(str.charAt(i-1) == str.charAt(i)){
                    samePoint.add(i);
                }
            }
            // 无论在哪一个重复的位置进行切割旋转，最终的最大长度总是等于：最后一个重复位置到尾部的长度+首部到第一个重复位置的长度
            int last = str.length() - samePoint.get(samePoint.size()-1);
            int left = samePoint.get(0);
            max = Integer.max(last+left, max);
            result = max;
        }
        return result;
    }
}
